/**
 * @author VernHe
 * @date 2021年05月16日 17:23
 */
public class Solution_076 {
    public static void main(String[] args) {
        System.out.println(new Solution_076().minWindow("ADOBECODEBANC","ABC"));
    }

    /**
     * 滑动窗口
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        // 参数判断
        if(s == null || t == null || s.length() == 0 || t.length() == 0) {
            return "";
        }
        int sLen = s.length();
        int tLen = t.length();
        // 定义变量
        // 字符的起始下标
        int start = 0;
        // 字符长度
        int size = Integer.MAX_VALUE;
        // 初始化need数组，用来记录那些字符是需要的，那些字符是不需要的
        int[] need = new int[128];
        for (int i = 0; i < tLen; i++) {
            need[t.charAt(i)]++;
        }
        // 还需要几个字符
        int needCnt = tLen;
        int left = 0,right = 0;

        // 循环遍历
        // 当窗口右边没有到达最后面的时候，一直循环
        while (right < sLen) {
            // 获取当前的字符
            char c = s.charAt(right);
            // 如果是需要的
            if (need[c] > 0) {
                needCnt--;
            }
            need[c]--;
            // 如果找到了符合要求的字符串
            if (needCnt == 0) {
                // 把左边界移动到合适的位置，即如果是不需要的字符就往右移
                while (left < right && need[s.charAt(left)] < 0) {
                    need[s.charAt(left)]++;
                    left++;
                }
                // 如果新的窗口比要来窗口的size小，就更新size和start
                int curSize = right - left + 1;
                if (curSize < size) {
                    size = curSize;
                    start = left;
                }
                // 上面处理完之后，窗口右移
                need[s.charAt(left)]++;
                left++;
                needCnt++;
            }
            // 如果不是需要的，窗口右边界继续右移
            right++;
        }

        // 返回结果
        return size == Integer.MAX_VALUE ? "" : s.substring(start,start + size);
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0){
            return "";
        }
        int[] need = new int[128];
        //记录需要的字符的个数
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        //l是当前左边界，r是当前右边界，size记录窗口大小，count是需求的字符个数，start是最小覆盖串开始的index
        int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;
        //遍历所有字符
        while (r < s.length()) {
            char c = s.charAt(r);
            if (need[c] > 0) {//需要字符c
                count--;
            }
            need[c]--;//把右边的字符加入窗口
            if (count == 0) {//窗口中已经包含所有字符
                while (l < r && need[s.charAt(l)] < 0) {
                    need[s.charAt(l)]++;//释放右边移动出窗口的字符
                    l++;//指针右移
                }
                if (r - l + 1 < size) {//不能右移时候挑战最小窗口大小，更新最小窗口开始的start
                    size = r - l + 1;
                    start = l;//记录下最小值时候的开始位置，最后返回覆盖串时候会用到
                }
                //l向右移动后窗口肯定不能满足了 重新开始循环
                need[s.charAt(l)]++;
                l++;
                count++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}
